//给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。 
//
// 整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4ˣ 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 16
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：n = 5
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：n = 1
//输出：true
// 
//
// 
//
// 提示： 
//
// 
// -2³¹ <= n <= 2³¹ - 1 
// 
//
// 
//
// 进阶：你能不使用循环或者递归来完成本题吗？ 
//
// Related Topics 位运算 递归 数学 👍 383 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2024-12-05 11:06:59
 * @description 342.4的幂
 
 */
 
public class PowerOfFour {
    public static void main(String[] args) {
    //测试代码
    PowerOfFour fun = new PowerOfFour();
    Solution solution= fun.new Solution();
        System.out.println(Math.pow(4,18)%2);
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        // 指数或者位运算
     /*
    4 不是质数，导致因数不唯一
    4 = 2^2，所以 4^k = 2^{2k}，它的因数可以是 2 的幂（如 2, 4, 8, 16, ...）。
    因此，4^k 的因数不一定是 4 的幂（比如 8 是 4^1.5 的因数，但不是 4 的幂）。

   (n & (n - 1)) == 0：确保 n 是 2 的幂（二进制只有一个 1）。
(n & 0x55555555) != 0：确保 1 出现在奇数位（0x55555555 的二进制是 01010101...）。
     * */

    public boolean isPowerOfFour(int n) {
        if (n <= 0) return false;
        // 4^k = (2^2)^k = 2^{2k}，所以二进制形式是 `1` 后面跟偶数个 `0`（如 100, 10000, ...）
        //*4 每次会左移两位
        return (n & (n - 1)) == 0  // 判断是否是 2 的幂（二进制只有一个 1）
                // 再判断0的个数
                && (n & 0x55555555) != 0;  // 判断 1 的位置是否在奇数位（如 1, 4, 16, ...）
    }
    //同理5 的幂因为5是质数所以可以这么处理
    public boolean isPowerOfFive(int n) {
        return n > 0 && 1220703125 % n == 0;
    }
    public boolean isPowerOfFive1(int n) {
        if (n <= 0) return false;
        double log5 = Math.log(n) / Math.log(5);  // 计算 log₅(n)
        return Math.abs(log5 - Math.round(log5)) < 1e-10;  // 判断是否为整数
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
